/**
 * @author: 最帅的的乐乐
 * @date: 2024-05-14 11:24 星期二
 * @motto the harder, the luckier。
 * Completed at @date: 2024-05-14 14:00
 */

public class _23_MergeKLists {
    private ListNode merge2Lists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }

        tail.next = l1 == null? l2: l1;

        return dummyHead.next;
    }
//逐一合并，时间复杂度：O(NK)
        public ListNode mergeKLists1(ListNode[] lists) {
            ListNode res = null;
            for (ListNode list: lists) {
                res = merge2Lists(res, list);
            }
            return res;
        }
        //两两合并，分治，时间复杂度：O(NlogK)
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        int k = lists.length;
        while (k > 1) {
            int idx = 0;
            for (int i = 0; i < k; i += 2) {
                if (i == k - 1) {
                    lists[idx++] = lists[i];
                } else {
                    lists[idx++] = merge2Lists(lists[i], lists[i + 1]);
                }
            }
            k = idx;
        }
        return lists[0];
    }
    public static void main(String[] args) {
        // 创建几个有序链表用于测试
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(4);
        list1.next.next = new ListNode(5);

        ListNode list2 = new ListNode(1);
        list2.next = new ListNode(3);
        list2.next.next = new ListNode(4);

        ListNode list3 = new ListNode(2);
        list3.next = new ListNode(6);

        // 构建一个 ListNode 数组，包含上面创建的三个链表链表数组如下：
        //[
        //  1->4->5,
        //  1->3->4,
        //  2->6
        //]
        ListNode[] lists = {list1, list2, list3};

        // 创建一个 Solution 对象
        _23_MergeKLists solution = new _23_MergeKLists();

        // 调用 mergeKLists 方法合并链表
        ListNode mergedList = solution.mergeKLists(lists);

        // 打印合并后的链表
        System.out.println("Merged List:");
        while (mergedList != null) {
            System.out.print(mergedList.val + "->");
            mergedList = mergedList.next;
        }
        System.out.println("null");
    }
}


